#include <stdlib.h>
#include <stdio.h>

#include "../../include/bitree.h"

static void print_preorder(const bitree_node_t *node)
{
	if (!bitree_eob(node)){
		fprintf(stdout, "node = %d\n", *(int *)bitree_data(node));

		if (!bitree_eob(bitree_left(node)))
			print_preorder(bitree_left(node));

		if (!bitree_eob(bitree_right(node)))
			print_preorder(bitree_right(node));
	}

	return;
}

static void print_inorder(const bitree_node_t *node)
{
	if (!bitree_eob(node)){
		if (!bitree_eob(bitree_left(node)))
			print_inorder(bitree_left(node));

		fprintf(stdout, "node = %d\n", *(int *)bitree_data(node));

		if (!bitree_eob(bitree_right(node)))
			print_inorder(bitree_right(node));
	}

	return;
}

static void print_postorder(const bitree_node_t *node)
{
	if (!bitree_eob(node)){
		if (!bitree_eob(bitree_left(node)))
			print_postorder(bitree_left(node));

		if (!bitree_eob(bitree_right(node)))
			print_postorder(bitree_left(node));

		fprintf(stdout, "node = %d\n", *(int *)bitree_data(node));
	}

	return;
}


static int insert_int(bitree_t *tree, int i)
{
	bitree_node_t *node, *prev;
	int *data, direction;

	node = tree->root;
	direction = 0;

	while (!bitree_eob(node)){
		prev = node;

		if (i == *(int *)bitree_data(node))
			return -1;

		if (i < *(int *)bitree_data(node)){
			direction = 1;
			node = bitree_left(node);
		}else{
			direction = 2;
			node = bitree_right(node);
		}
	}

	if (!(data = (int *)malloc(sizeof(int))))
		return -1;

	*data = i;

	if (direction == 0)
		return bitree_insert_left(tree, NULL, data);

	if (direction == 1)
		return bitree_insert_left(tree, prev, data);

	if (direction == 2)
		return bitree_insert_right(tree, prev, data);

	return -1;
}


static bitree_node_t *search_int(bitree_t *tree, int i)
{

	bitree_node_t *node;

	node = bitree_root(tree);

	while (!bitree_eob(node))
	{
		if (i == *(int *)bitree_data(node))
			return node;

		if (i < *(int *)bitree_data(node))
			node = bitree_left(node);
		else
			node = bitree_right(node);
	}

	return NULL;
}


int main(int argc, char *argv[])
{
	bitree_t tree;
	bitree_node_t	*node;
	int i;

	bitree_init(&tree, free);
	fprintf(stdout, "inserting some nodes\n");

	if (insert_int(&tree, 20))
		return 1;

	if (insert_int(&tree, 10))
		return 1;

	if (insert_int(&tree, 30))
		return 1;
		
	
	if (insert_int(&tree, 15))
		return 1;

	if (insert_int(&tree, 25))
		return 1;

	if (insert_int(&tree, 70))
		return 1;
		
	if (insert_int(&tree, 80))
		return 1;

	if (insert_int(&tree, 23))
		return 1;

	if (insert_int(&tree, 26))
		return 1;
		
	if (insert_int(&tree, 5))
		return 1;

	fprintf(stdout, "Tree size is %d\n", bitree_size(&tree));
	fprintf(stdout, "(Preorder traversal)\n");
	print_preorder(bitree_root(&tree));

	i = 30;
	//i = 99;
	if (!(node = search_int(&tree, i)))
		fprintf(stdout, "can not find %d\n", i);
	else {
		fprintf(stdout, "find %d...removing left tree below it\n", i);
		bitree_remove_left(&tree, node);
		fprintf(stdout, "tree size is %d\n", bitree_size(&tree));
		fprintf(stdout, "(Preoder traversal)\n");
		print_preorder(bitree_root(&tree));
	}

	
	i = 20;
	if (!(node = search_int(&tree, i)))
		fprintf(stdout, "can not find %d\n", i);
	else {
		fprintf(stdout, "find %d...removing left tree below it\n", i);
		bitree_remove_right(&tree, node);
		fprintf(stdout, "tree size is %d\n", bitree_size(&tree));
		fprintf(stdout, "(Preoder traversal)\n");
		print_preorder(bitree_root(&tree));
	}

	i = bitree_is_leaf(bitree_root(&tree));
	fprintf(stdout, "Testing bitree_is_leaf...Value=%d (0=OK)\n", i);
	i = bitree_is_leaf(bitree_left((bitree_root(&tree))));
	fprintf(stdout, "Testing bitree_is_leaf...Value=%d (0=OK)\n", i);
	i = bitree_is_leaf(bitree_left(bitree_left((bitree_root(&tree)))));
	fprintf(stdout, "Testing bitree_is_leaf...Value=%d (1=OK)\n", i);
	i = bitree_is_leaf(bitree_right(bitree_left((bitree_root(&tree)))));
	fprintf(stdout, "Testing bitree_is_leaf...Value=%d (1=OK)\n", i);

	fprintf(stdout, "Inserting some nodes\n");

	if (insert_int(&tree, 55) != 0)
	   return 1;

	if (insert_int(&tree, 44) != 0)
	   return 1;

	if (insert_int(&tree, 77) != 0)
	   return 1;

	if (insert_int(&tree, 11) != 0)
	   return 1;

	fprintf(stdout, "Tree size is %d\n", bitree_size(&tree));
	fprintf(stdout, "(Preorder traversal)\n");
	print_preorder(bitree_root(&tree));
	fprintf(stdout, "(Inorder traversal)\n");
	print_inorder(bitree_root(&tree));
	fprintf(stdout, "(Postorder traversal)\n");
	print_postorder(bitree_root(&tree));

	fprintf(stdout, "Destroying the tree\n");
	bitree_destroy(&tree);
	
	return 0;
}
